1. Field of the Invention
The present invention relates to a method of and an apparatus for placing blocks in a semiconductor integrated circuit, and more particularly to a method of and an apparatus for placing blocks in the ASICs (for example, SOG, sea of gates, Embedded Array and Standard cell) which make it possible to fully automatically design a floorplan of the ASIC by means of a computer aided design (CAD) apparatus.
2. Description of the Related Art
For one design method of the ASICs, the SOG is known as a highly integrated circuit which permits the placement and routing of cells in desired regions of a chip. In this SOG, when determining the placement and routing of cells, a hierarchical design method is adopted in which, instead of laying out small transistors from the outset, routing is first effected after functions are divided and regions are allotted in units of large macro cells, and routing of interconnections is then carried out by placing the small transistors in the large macro cells.
In this hierarchical design method, the macro cells each having a certain size and a certain shape are placed within a die of a predetermined size such that the routing length between macro cells becomes minimum. This placement presents a problem of cutting small plates out of a large plate, and the number of combinations of placement is infinite.
For this reason, the placement of macro cells and adjustment of the shape are performed manually through trial and error by using an interactive-type graphics screen of a development tool for CAD, requiring a time-consuming operation.
As an example of development tools such as the one mentioned above, for instance, Japanese Patent Unexamined Publication No. 181348/1988 discloses an apparatus for designing the layout of an LSI of a hierarchical-type layout method, comprising: a layout specification storage unit; a rough layout determining means; a rough layout information storage unit; a block layout determining means; a block layout information storage unit; a chip layout determining means; a chip layout information storage unit; and a mask pattern synthesizing means.
As an example of a very large-scale integrated circuit (VLSI) using the above-described hierarchical design method, a technique for semi-automatically designing a chip floorplan for placement of block levels, i.e., a first stage of layout, has been proposed in, for instance, the "Note of Design Automation Group, Information Processing Society of Japan, 18-3 (Sept. 1983)." In this technique, using an attractive and repulsive force method (AR method), the initial placement of blocks is first conducted by using a spring model of a mass system in which sizeless blocks are interconnected by springs. Then, in this placement, the size of each block is given in the shape of a rectangle corresponding to an actual shape, and block packing processing is effected wherein each block is moved manually through trial and error such that the overlapping of blocks is eliminated, and distant blocks are brought close to each other. In addition, in a latter half of processing, overlapping is eliminated by manually changing the aspect ratio of each block whose shape is variable. Furthermore, an area necessary for routing among blocks is calculated on the basis of information on interconnections between blocks and positional information on blocks.
Meanwhile, a block placement technique is proposed in the Transactions of the Institute of Electronics, Information and Communication Engineers of Japan, 89/1, Vol. J72-A No. 1, in which a dynamic model is set wherein there are exerted on the circuit blocks attractive force corresponding to both the number of interconnections and the distance and repulsive force corresponding to the area of overlapping. In this block placement technique, the blocks are initially placed within the die frame only by means of the attractive force due to the interconnections so as to minimize the square-sum of the routing length. Subsequently, with respect to this placement repulsive force is gradually increased with an initial value 1/100 times the attractive force, and overlap is gradually eliminated by repeated calculation such that the ratio of an overlapping area to the total area of the blocks becomes 8.2% or less. Thus, the relative positional relationship of the blocks is substantially defined. Then, orientations of the blocks are examined consecutively starting with a block most distant from the center of the layout region. Finally, balanced positions of the blocks are determined, and the orientations of the blocks are rechecked to determine the layout of the blocks.
In this method, there remains slight overlapping which balances with the attractive force due to interconnections. Therefore, a modified technique has been proposed for obtaining an overlap-free layout by enlarging the blocks in advance by slight lengths prior to placement, gradually eliminating the overlap until a maximum overlapping length between the blocks becomes less than the amount of that enlargement, and finally returning the blocks to their original sizes.
In the above-described techniques, however, all the blocks are processed as rectangles and hence movement thereof are not easy. Further, in the latter technique, the aspect ratio (vertical to lateral ratio) of each block is not adjusted. Accordingly, there are cases where a compact placement is not necessarily attained as a whole particularly if variable-shape blocks, such as soft macro cells whose aspect ratio is variable, are used. Further, in the above-described techniques the positions of the blocks are moved within the die frame to eliminate overlaps among the blocks which were produced in the initial placement. Accordingly, the block positions may be moved in excess in the process of determination of the layout, with the result that the conditions of such as the total routing length being minimum and the dead space being minimum are lost.
To overcome the above-described problems, the present inventors have proposed a method of placing and routing blocks in a highly integrated circuit in U.S. patent application Ser. No. 07/543,549, now U.S. Pat. No. 5,309,371 . In this method, sizeless blocks are initially placed by using a spring model of a mass system in which the blocks are interconnected by springs, the sizes of at least some blocks are given by circles, and the blocks are placed anew such that overlapping of the blocks is eliminated. Then, the outer shapes of the blocks are made compact in conformity with the die frame, the shapes of the blocks are changed from the circles to actual shapes, the blocks are expanded, regions for routing are allotted, and the aspect ratios of the blocks are adjusted. As a result, the minimization of the total routing length and the compact placement of the blocks can be effected automatically, and the aspect ratios (shapes) of the blocks can be determined automatically.
A mass-point model in which blocks are regarded as mass points and routing between blocks is regarded as attractive spring force so as to place the blocks by means of the balance of attractive force is disclosed in "PROUD; A Fast Sea-Of-Gates Placement Algorithm," 25th ACM/IEEE DAC, pp. 318-322, 1988.
However, according to the semi-automatic graphics interactive floorplans based on a manual operation or using a dynamic model only in the initial placement, which are disclosed in Japanese Patent Unexamined Publication No. 181348/1988 and in the "Note of Design Automation Group, Information Processing Society of Japan, 18-3 (Sept. 1983)," there has been a problem in that many manhours are involved in the operation.
In addition, according to the method using the dynamic model in which repulsive force is exerted on the blocks, which is disclosed in the Transactions of the Institute of Electronics, Information and Communication Engineers of Japan, 1989/1, Vol. J72-A No. 1, there has been a problem in that much processing time is required for repeated calculation for obtaining the balance of force.
Furthermore, according to the method of making blocks compact by using a dynamic model in which attractive force and repulsive force act, which is proposed in U.S. patent application Ser. No. 07/543,549 filed by the present inventors, it is necessary to take a number of processing steps in designing a floorplan, including the alteration of the shape. Hence, there has been the problem that much processing time is involved.